import bisect



# 1. __getitem__
# 2. append
# 3. flush

class StringList:
	def __init__(self):
		self.texts = []
		self.sizes = [-1]
		self.base = 0
	def __getitem__(self, offset):
		abs = self.base + offset
		(i, offset) = self.findIndex(abs)
		text = self.texts[i]
		return text[offset]
	def __len__(self):
		size = self.sizes[-1] + 1 - self.base
		return size
	def __str__(self):
		return ''.join(self.texts)
	
	def findIndex(self, abs):
		i = bisect.bisect_left(self.sizes, abs) - 1
		return (i, abs - self.sizes[i] - 1)
	def flush(self, base):
		if base > (self.sizes[-1] + 1):
			print "base=%d size=%d" % (base, self.sizes[-1]+1, )
			raise Exception("Out of range")
		(index, offset) = self.findIndex(base)
		self.base = offset
		if index <= 0:
			return
		del self.texts[:index]
		del self.sizes[:index]
		diff = self.sizes[0] + 1
		for i in xrange(len(self.sizes)):
			self.sizes[i] -= diff
	def shift(self, offset):
		self.flush(self.base + offset)
	def append(self, elem):
		if not elem:
			return
		self.texts.append(elem)
		self.sizes.append(self.sizes[-1] + len(elem))



def testStringList():
	import os

	print "testStringList()"
	length = 1000
	loops = 100
	prime = 31
	phrases = [os.urandom(length) for i in xrange(loops)]
	text = ''.join(phrases)
	
	buf = StringList()
	for i in xrange(loops):
		buf.append(phrases[i])
		if len(buf.texts) + 1 != len(buf.sizes):
			raise Excaption("Broken data structure")
	
	for i in xrange(len(text)):
		if buf[i] != text[i]:
			raise Exception("Wrong char")
	for i in xrange(len(text)):
		j = i % prime
		if i > 0 and j == 0:
			buf.shift(prime)
		if buf[j] != text[i]:
			print "i=%d j=%d" % (i, j, )
			raise Exception("Wrong char")
		if len(buf.texts) + 1 != len(buf.sizes):
			raise Excaption("Broken data structure")

def testRussian():
	import os
	import random
	
	print "testRussian()"
	probAppend = 0.01
	probShift  = 0.02 + probAppend
	dataSize = 2000
	iteration = 1000 * 100
	
	buf = StringList()
	for i in xrange(iteration):
		r = random.random()
		if r < probAppend:
			size = random.randrange(dataSize)
			buf.append( os.urandom(size) )
		if r < probShift:
			bufLen = len(buf)
			if bufLen > 0:
				size = random.randrange(bufLen)
				buf.shift( size )
		else:
			size = len(buf)
			if size > 0:
				c = buf[ random.randrange(size) ]

if __name__ == '__main__':
	testStringList()
	testRussian()
